package 线段树And树状数组;

public class leetcode307区域和检索And数组修改 {
	public static void main(String [] args) {
		int nums [] = {1,3,5};
		NumArray tree = new NumArray(nums);
		tree.sumRange(1, nums.length, 1);
		System.out.println(tree.sum[1]);
//		int ans = tree.query(1, nums.length, 1, 1, 1);
		tree.update(1, 1, 5, 1, nums.length, 1);
		System.out.println(tree.sum[1]);
		int ans = tree.query(1, nums.length, 1, 3, 1);
		System.out.println(ans);
		tree.update(2, 2, 5, 1, nums.length, 1);
		int ans1 = tree.query(1, nums.length, 1, 3, 1);
		System.out.println(ans1);
	}

}
class NumArray{
	int nums [];
	int sum[] ;
	int change[];
	boolean update[];
	public NumArray(int nums[]) {
		this.nums = new int [nums.length + 1];
		for(int i = 0; i< nums.length; i++) {
			this.nums[i+1] = nums[i];
		}
		sum = new int [nums.length << 2];
		change = new int [nums.length << 2];
		update = new boolean [nums.length << 2];
	}
	public void pushUp(int index) {
		sum[index] = sum[index << 1] +sum[index << 1 | 1];
		return ;
	}
	
	public void pushDown(int l,int r,int index) {
		if(update[index]) {
			/**
			 * 如果 update[index] == true  需要 下发
			 * 上一次的 操作 所累积的 信息 量 
			 */
			int value = change[index];
			int mid = l + r >> 1;
			change[index << 1] = value;
			update[index << 1] = true;
			change[index << 1 | 1] =value;
			update[index << 1 | 1] = true;
			sum [index << 1] = (mid  - l +1) * value;
			sum [index << 1 | 1] = (r - mid ) *value;
			update[index] = false;
		}
	}
	public void sumRange(int l,int r,int index) {
		if(l == r) {
			sum[index] =nums[r];
			return ;
		}
		int mid = l + r >>1;
		sumRange(l,mid,index << 1);
		sumRange(mid + 1,r,index << 1 | 1 );
		/**
		 * 其实 这个  步骤 有点      树形   dp 的 味道了 
		 */
		pushUp(index);
	}
	/**
	 *我感觉 这样 指定修改  numsIndex  位置上的 值 那不如 直接修改 L ，R 区间 位置上的 值 不过 这里 
	 *L == R   
	 *用   大写  字母   表示  待修改的区间 用小写 字母 表示 nums  数组的区间 
	 *
	 */
	public void update(int L,int R,int value,int l,int r,int index) {
		if(L <=r &&  r <= R ) {
			update[index] = true;
			change[index] = value;
			sum[index] = (r - l + 1) * value;
			return ;
		}
		int mid = l + r >> 1;
		pushDown(l,r,index);
		if(L <= mid ) {
			update(L,R,value,l,mid,index << 1);
		}
		if(R > mid) {
			update(L,R,value,mid + 1,r,index << 1 | 1);
		}
//          这个 pushUp 非常的 重要  注意 这个 是 递归啊 
 		pushUp(index);
	}
	public void update(int numsIndex,int value) {
		
	}
	/**
	 *  这几个 操作 很多 都是 递归 
	 *  要注意 这一点 
	 *  其实 操作 并不麻烦 对吗 
	 *  主要 是 细节 很多
	 */
	public int  query(int l,int r,int L ,int R,int index) {
		if(L <= l &&  r <= R) {
			return sum[index];
		}
		int mid = l + r >>1;
		pushDown(l,r,index);
		int ans = 0;
		if(L <= mid) {
			ans += query(l,mid,L,R,index << 1);
		}
		if(R > mid ) {
			ans += query(mid + 1,r,L,R,index << 1 | 1);
		}
		return ans;
	}
}